// Passgen.cpp
//


#include <stdio.h>


//--------------------------------------------------------------------

template <class T>
class ListItem
{
public:

    T           item;
    ListItem*   pNext;


    ListItem( T t )
    {
        item  = t;
        pNext = NULL;
    }

   ~ListItem()
    {
        if( pNext )  delete pNext;
    }

};


template <class T>
class List                          // List of ListItems
{
    ListItem<T>**   ppListNext;     // For Appending to Tail

public:

    ListItem<T>*    pList;


    List()
    {
        pList = NULL;
        ppListNext = &pList;
    }

   ~List()
    {
        if( pList )  delete pList;
    }


    void Append( T t )              // Appending to Tail
    {
        ListItem<T>* pNew = new ListItem<T>( t );

       *ppListNext =  pNew;
        ppListNext = &pNew->pNext;
    }

};


//--------------------------------------------------------------------

class Counter;

typedef ListItem<Counter*> CounterItem;


class Counter : public List<Counter*>
{
public:

   ~Counter()
    {
        for( CounterItem* p = pList; p; p = p->pNext )
            delete p->item;
    }

    // Virtuals

    virtual void Reset()
    {
        for( CounterItem* p = pList; p; p = p->pNext )
            p->item->Reset();
    }

    virtual bool Next()
    {
        for( CounterItem* p = pList; p; p = p->pNext )
        {
            if( p->item->Next() )
                return true;
        
            p->item->Reset();
        }

        return false;
    }

};


//--------------------------------------------------------------------

int strlen( const char* c )  {  for( int i=0; *c ++; i++ );  return i; }


class Alphabet
{
public:

    const char* pChars;
    char        nLength;        // Length of Alphabet

    Alphabet( const char* c )
    {
        pChars  = c;
        nLength = strlen( c );
    }

};


//--------------------------------------------------------------------
// Letter of Alphabet

class Letter : public Counter
{
    Alphabet*   pAlphabet;
    char        nIndex;         // Index of Char in Alphabet

public:

    Letter( Alphabet* a )
    {
        pAlphabet = a;
    }

    // Override Virtuals for Letter

    void Reset()
    {
        nIndex = 0;
    }

    bool Next()
    {
        if( ++nIndex < pAlphabet->nLength )  // Next?
            return true;

        nIndex = 0; // Reset
        return false;
    }


    // For Catenation
    char Get()  {  return pAlphabet->pChars[nIndex]; }

};


//--------------------------------------------------------------------


class Word : public Counter
{
public:

    Word( int n, Alphabet* a )
    {
        for( ; n; n-- )
            Append( new Letter( a ) );
    }

};


//--------------------------------------------------------------------

typedef int COMB;


// Factorial
int fact( int n )  {  return  n<=1 ?  1 : n * fact(n-1); }

// Count of "1"-bits in Combination
char bitn( COMB n )  {  for( char b=0; n; n>>=1 ) if( n&1 ) b++;  return b; }




class Comb : public Counter
{
    COMB*   pCombs;     // Combinations
    int     nCount;
    int     nIndex;

public:

    Comb( int k, int l )
    {
        nCount = fact(k+l) / fact(k) / fact(l);
        pCombs = new COMB[nCount];

        COMB comb = 0;
        for( int i=0; i<nCount; comb++ )
            if( bitn(comb) == l )           // Is Combination Valid?
                pCombs[ i++ ] = comb;       // Save Combination
    }
   ~Comb()
    {
        delete[] pCombs;
    }

    // Override Virtuals for Combinations

    void Reset()
    {
        nIndex = 0;
    }

    bool Next()
    {
        if( ++nIndex < nCount ) // Next?
            return true;

        nIndex = 0; // Reset
        return false;
    }


    // For Catenation
    COMB    Get()  {  return pCombs[nIndex]; }

};


//--------------------------------------------------------------------
// Tree of Password Catenation

class TreeItem
{
public:
    virtual void ResetCat() {}
    virtual void Cat( char* ) {}
};


class CombTreeItem : public TreeItem
{
public:

    Comb*           pComb;

    TreeItem*       pChilds[2];  // Binary Tree

    char            nCombPos;    // Catenation position

    // Construction

    CombTreeItem( TreeItem* p0, TreeItem* p1, Comb* pC )
    {
        pChilds[0] = p0;
        pChilds[1] = p1;
        pComb      = pC;        // Link Comb for Catenation
    }
   ~CombTreeItem()
    {
        delete pChilds[0];
        delete pChilds[1];
    }

    // Virtuals

    void ResetCat()
    {
        nCombPos = 0;
        pChilds[0]->ResetCat();
        pChilds[1]->ResetCat();
    }

    void Cat( char* sz )
    {
        pChilds[ pComb->Get() >> nCombPos++ & 1 ]->Cat( sz );
    }

};

class WordTreeItem : public TreeItem
{
public:
    
    Word*       pWord;
    Alphabet*   pAlphabet;      // Keep It Here

    CounterItem*    pWordPos;   // Catenation position

    // Construction

    WordTreeItem( Alphabet* pA, Word* pW )
    {
        pAlphabet = pA;
        pWord     = pW;         // Link Word for Catenation
    }

   ~WordTreeItem()
    {
        delete pAlphabet;
    }

    // Virtuals

    void ResetCat()
    {
        pWordPos = pWord->pList;
    }

    void Cat( char* sz )
    {
       *sz = ((Letter*)pWordPos->item)->Get();
        pWordPos = pWordPos->pNext;
    }

};


class Tree : public Counter
{
public:

    TreeItem*   pRoot;
    int         nLength;    // Length of Full Password


    Tree()
    {
        pRoot   = NULL;
        nLength = 0;
    }

   ~Tree()
    {
        if( pRoot )  delete pRoot;
    }


    void Add( const char* c, int n )
    {
        if( !n )  return;
            
        Alphabet* pA = new Alphabet(c);

        Word* pWord = new Word( n, pA );
        Append( pWord );        // Add to Counter
        
        TreeItem* pNew = new WordTreeItem( pA, pWord );     // WordItem is needed always

        if( pRoot )                                         // If it was Tree
        {
            Comb* pComb = new Comb( n, nLength );
            Append( pComb );    // Add to Counter

            pNew = new CombTreeItem( pNew, pRoot, pComb );  // Add Combination too
        }

        nLength += n;

        pRoot = pNew;
    }


    void Cat( char* sz )
    {
        if( !pRoot )  return;

        pRoot->ResetCat();

        char* c = sz + nLength;

        while( c != sz )
            pRoot->Cat( --c );      // Fill the Password Backwards
    }

};


//--------------------------------------------------------------------

int toInt( char* s )  {  for( int n=0; *s; s++ )  n = n * 10 + (0xF & *s);  return n;  }


int main( int argc, char* argv[] )
{

    printf("bntr Passgen\n");
    printf("passgen.exe n c l limit outputfile\n");
    printf("n - count of numerals\n");
    printf("c - count of capital letters\n");
    printf("l - count of small letters\n");

    if( argc == 1 )
        return 0;


    // Build Tree

    char* cAlphabets[3] = { "0123456789",
                            "ABCDEFGHIJKLMNOPQRSTUVWXYZ",
                            "abcdefghijklmnopqrstuvwxyz" };
    Tree tree;

    for( int i=1; i<=3 && i<argc; i++ )
        tree.Add( cAlphabets[i-1], toInt( argv[i] ) );

    tree.Reset();


    // Output Passwords 

    int nLimit = argc > 4 ?  toInt( argv[4] ) : 0;

    FILE* fFile = argc > 5 ? fopen( argv[5], "a" ) : stdout;

    char szPass[0x100] = {0};


    do  {
        tree.Cat( szPass );
        fprintf( fFile, "%s\n", szPass );
    } 
    while( (!nLimit || --nLimit)  &&  tree.Next() );


    if( argc > 5 ) fclose( fFile );

    return 0;
}